/**
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package item07;

import org.junit.Assert;
import org.junit.Test;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:ConstructBinaryTree.java v1.0 2018/7/14 上午10:19 LvJing Exp $
 */
public class ConstructBinaryTree {

    /*
    重构二叉树：目前已知某二叉树的前序遍历和中序遍历的结果，且都不含重复数字，尝试重新构建该二叉树。
    思路：前序遍历能知道根节点的值，在对比中序遍历，能知道根节点在中序遍历的位置，通过这个位置就能知道这个根节点的左右子树分别是什么，即第一次
    递归知道根节点，左子树序列，右子树序列，如果左右子树不为一个节点的话，可以再次以该方式获取左右子树的根节点，不断递归即可。
     */

    private TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null) {
            return null;
        }

        if (pre.length != in.length) {
            return null;
        }

        return constructCore(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    /*
     * 前序序列 1,2,4,7,3,5,6,8     后序序列 4,7,2,1,5,3,8,6
     * 1,2,3    3,1,2
     */
    private TreeNode constructCore(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        if (endPre < startPre || endIn < startIn) {
            return null;
        }

        if (startPre == endPre) {
            // 前序只有一个节点，中序肯定只有一个节点
            if (startIn != endIn) {
                throw new IllegalArgumentException();
            }

            // 中序和前序不符合
            if (pre[startPre] != in[startIn]) {
                throw new IllegalArgumentException();
            }

            return new TreeNode(pre[startPre]);
        }

        int rootValue = pre[startPre];
        TreeNode root = new TreeNode(rootValue);

        for (int i = startIn; i <= endIn; i++) {
            // 根据中序找到根节点位置
            if (rootValue == in[i]) {
                // 构造左子树
                root.left = constructCore(pre, startPre + 1, i - startIn + startPre, in, startIn, i - 1);
                // 构造右子树
                root.right = constructCore(pre, i - startIn + startPre +1, endPre, in, i + 1, endIn);
            }
        }
        return root;
    }

    class TreeNode {
        int      value;
        TreeNode left;
        TreeNode right;

        TreeNode(int value, TreeNode left, TreeNode right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        TreeNode(int value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;

            TreeNode treeNode = (TreeNode) o;

            if (this.left != null) {
                if (!this.left.equals(treeNode.left)) {
                    return false;
                }
            }

            if (this.right != null) {
                if (!this.right.equals(treeNode.right)) {
                    return false;
                }
            }

            return this.value == treeNode.value;
        }
    }

    /**
     * 输入的二叉树，根节点为空
     */
    @Test
    public void test01() {
        Assert.assertNull(reConstructBinaryTree(null, null));
    }

    /**
     * 二叉树的前序序列和中序序列不匹配
     */
    @Test(expected = IllegalArgumentException.class)
    public void test02() {
        reConstructBinaryTree(new int[] { 1, 2, 3 }, new int[] { 3, 1, 2 });
    }

    /**
     * 所有节点都没有右子节点的二叉树
     */
    @Test
    public void test03() {
        TreeNode expect = new TreeNode(1, new TreeNode(2, new TreeNode(3, null, null), null), null);
        Assert.assertEquals(expect, reConstructBinaryTree(new int[] { 1, 2, 3 }, new int[] { 3, 2, 1 }));
    }

    /**
     * 所有节点都没有左子节点的二叉树
     */
    @Test
    public void test04() {
        TreeNode expect = new TreeNode(1, null, new TreeNode(2, null, new TreeNode(3, null, null)));
        Assert.assertEquals(expect, reConstructBinaryTree(new int[] { 1, 2, 3 }, new int[] { 1, 2, 3 }));
    }

    /**
     * 只有一个节点的二叉树
     */
    @Test
    public void test05() {
        TreeNode expect = new TreeNode(1, null, null);
        Assert.assertEquals(expect, reConstructBinaryTree(new int[] { 1 }, new int[] { 1 }));
    }

    /**
     * 完全二叉树
     */
    @Test
    public void test06() {
        TreeNode expect = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
        Assert.assertEquals(expect, reConstructBinaryTree(new int[] { 1, 2, 4, 5, 3 }, new int[] { 4, 2, 5, 1, 3 }));
    }

    /**
     * 不完全二叉树
     */
    @Test
    public void test07() {
        TreeNode expect = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4), null));
        Assert.assertEquals(expect, reConstructBinaryTree(new int[] { 1, 2, 3, 4 }, new int[] { 2, 1, 4, 3 }));
    }
}
